Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
/
Розрахункова робота
з дисципліни
«Теорія алгоритмів»
Варіант - 5
ЛЬВІВ 2015
Зміст
Індивідуальне завдання.
Покроковий опис алгоритму.
Програмна реалізація.
Приклад роботи програми
Висновок.
Індивідуальне завдання
Дванадцять чисел, оточуючи фортецю, вирішили розташуватись так, щоб їхня сума вздовж кожної сторони шестикутника дорівнювала 17. Чотири числа вже знаходяться на своїх місцях. Як треба розташувати решту вісім чисел?
Покроковий опис алгоритму
Створюємо масив для збереження числової послідовності та масив для визначення, чи число використовувалося, чи ні.
Вводимо у масив числової послідовності дані, які задані умовою, тобто числа 9, 6, 2 і 12 уже знаходяться на своїх місцях.
Масив, який містить логічні true і false повністю заповнюємо значеннями true(число вільне), а окремі елементи, які відповідають числам, котрі уже на своїх місцях, заповнимо значеннями false(число зайняте).
Пошук наступного потрібного числа розпочинаємо з 5 елемента, оскільки перші 4 уже задані. Пошук здійсюємо за допомогою окремої функції, котра шукає вільне число і повертає його або -1, якшо вільних чисел немає.
Якщо послідовність пройдена до кінця(12) і програма вийшла за межі послідовності, і зупинилася знову на першому елементі, то рахуємо суму.
Якщо сума правильна, то потрібна послідовність знайдена.
Якщо крок не за межами послідовності, то перевіряємо чи це не перетин сторін. Якщо це перетин, то заповнюємо елемент масиву послідовності числом поки не буде знайдено потрібної суми. Якщо такого числа не знайшлося, то повертаємось.
Якщо цикл зупинився на звичайному елементі, який не є перетином сторін, то шукаємо для нього число.
Пошук числа відбувається наступним чином: В функцію пошуку передається останнє число, яке ми присвоїли елементу(початково воно -1), беремо наступне після останнього і починаємо пошук поки не досягнемо максимального числа(12).
Функція повертає знайдене число. Якщо число не знайдеться. Функція повертає -1 і цикл по послідовності повертається назад.
Якщо ж ми отримали негативний результат пошуку послідовності з наступних кроків циклу, то спробуємо підставити інше число і для пошуку задаємо наступне після останнього число, яке ми вставили.
Програмна реалізація
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <cstdlib>
#define N 12
int searchNum(int last, bool c[N])
{
for (int i = last; i<N; i++)
if (c[i])
return i;
return -1;
}
bool search(int mas[N], bool c[N], int i)
{
if (i == 12)
{
if ((mas[i - 2] + mas[i - 1] + mas[0]) == 17)
{
printf("%d+%d+%d=%d\n", mas[i - 2], mas[i - 1], mas[0], mas[i - 2] + mas[i - 1] + mas[0]);
return true;
}
else
return false;
}
else
if (i % 2 == 0 && i != 0)
{
int last = -1;
int sum = 0;
do
{
if (last != -1)
c[last] = true;
last = searchNum(last + 1, c);
if (last == -1)
return false;
c[last] = false;
mas[i] = last + 1;
sum = mas[i - 2] + mas[i - 1] + mas[i];
}
while (sum<17);
if (sum == 17)
if (search(mas, c, i + 1))
{
printf("%d+%d+%d=%d\n", mas[i - 2], mas[i - 1], mas[i], mas[i - 2] + mas[i - 1] + mas[i]);
return true;
}
else
{
c[last] = true;
return false;
}
else
{
c[last] = true;
return false;
}
}
else
{
int last = -1;
do
{
if (last != -1) c[last] = true;
last = searchNum(last + 1, c);
if (last == -1) return false;
c[last] = false;
mas[i] = last + 1;
while (!search(mas, c, i + 1));
}
}
int main()
{
bool c[N];
int mas[N];
for (int i = 0; i<N; i++)
{
c[i] = true;
}
c[8] = c[5] = c[1] = c[11] = false;
mas[0] = 9;
mas[1] = 6;
mas[2] = 2;
mas[3] = 12;
if (search(mas, c, 4))
for (int j = 0; j<12; j++)
printf("%d ", mas[j]);
_...
